package J.算法.排序;

import java.util.Arrays;

/**
 * 排序算法的学习--按照升序顺序走
 */
public class A_SortStudy {
    public static void main(String[] args) {

        int[] arr = new int[]{31,34,53,21,60,84,9};

        //BubbleSort(arr);
      //  SelectSort(arr);
      // insertSort(arr);
    //    shellSort(arr);

    //    quickSort(arr,0, arr.length-1);
//
//        mergeSort(arr,0,arr.length-1);
//        System.out.println("arr="+Arrays.toString(arr));
        radixSort(arr);



    }

    /**
     * 1----冒泡排序：时间复杂度 n^2
     * @param arr
     */
    public static void BubbleSort(int[] arr){

        int temp = 0;
        for (int i =0;i<arr.length-1;i++){

            boolean flag_change = true;//优化--添加交换标志
            //每次走一趟 最后面的是有序的
            for (int j=0;j<arr.length-1-i;j++){
                if (arr[j]>arr[j+1]){
                    flag_change = false;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

            if (flag_change){
                //证明一次都没有交换过
                break;
            }

            System.out.println("第"+(i+1)+"趟结果：");
            System.out.println(Arrays.toString(arr));
        }

    }
    /**
     * 选择排序--举例从小到大排
     *  时间复杂度仍然是n^2
     *  但是因为其内部交换操作比冒泡少了很多 所以速度会更快
     */
    public static void SelectSort(int[] arr){

        //第一个for循环来判断轮数
        for (int r =1;r<arr.length;r++){
            int minIndex = r-1;
            int temp =0;

            for (int i=r;i<arr.length;i++){
                if (arr[i] < arr[minIndex]){
                    minIndex = i;
                }
            }

            //优化：如果minIndex并没有发生修改 就不需要交换
            if (minIndex != r-1){
                temp = arr[r-1];
                arr[r-1] = arr[minIndex];
                arr[minIndex] = temp;

                System.out.println("第"+(r)+"趟结果：");
                System.out.println(Arrays.toString(arr));

            }

        }

    }

    /**
     * 直接插入排序-参考打麻将码排
     */
    public static  void insertSort(int[] arr){


        for (int i=1;i<arr.length;i++){
            //把声明放在外面更好一些
            int insertVal = arr[i];//现保存起来需要插入的数值 便于后面移动
            int searchIndex = i-1;


            //寻找插入位置
            while (searchIndex>=0 && arr[searchIndex]>insertVal){
                //因为之前已经把要移动的取出来了 所以可以直接覆盖表示后移
                arr[searchIndex+1] = arr[searchIndex];
                searchIndex--;
            }
            //插入--注意这里插入的位置
            arr[searchIndex+1] = insertVal;



            System.out.println("第"+(i)+"趟结果：");
            System.out.println(Arrays.toString(arr));
        }

    }

    /**
     * 希尔排序
     */

    public static  void shellSort(int[] arr){

        int temp = 0;
        //第一轮排序--长度为10时 分为5组 第二轮就5/2=2组  第三轮 就是2/2=1组
//        for (int i= 5;i<arr.length;i++){
//            //这里步长为5--因为后面的两两调整之后还需要跟之前的进行对比
//            for (int j= i-5;j>=0;j-=5){
//                if (arr[j] > arr[j+5]){
//                    temp = arr[j];
//                    arr[j] = arr[j+5];
//                    arr[j+5] = temp;
//                }
//            }
//        }

        int count =0;
        //综合--法1交换法：最外层的循环以group为条件 每次/2 直到》0
//        for (int group =arr.length/2;group>0;group /= 2 ){
//            for (int i= group;i<arr.length;i++){
//                //这里步长为5--因为后面的两两调整之后还需要跟之前的进行对比
//                for (int j= i-group;j>=0;j-=5){
//
//                    //如果前面比后面大 就交换 最内侧的for循环有点类似于冒泡
//                     if (arr[j] > arr[j+group]){
//                        temp = arr[j];
//                        arr[j] = arr[j+group];
//                        arr[j+group] = temp;
//                    }
//                }
//            }
//
//            System.out.println("第"+(++count)+"趟结果：");
//            System.out.println(Arrays.toString(arr));
//        }


        //法2--上面的方法在交换过程中过于浪费时间 所以采用移位法--内部与插入法类似
        for (int gap=arr.length/2;gap>0;gap /= 2){

            for (int i= gap;i<arr.length;i++){
                int j = i;
                int tem = arr[j];

                //分组不单单是两个元素 插入排序里的while
                while (j-gap >=0 && tem < arr[j-gap] ){
                    arr[j] = arr[j-gap];
                    j -= gap;
                }

                //这里插入跟上面插入法的位置有些出入 原因是因为原来那个是以被遍历点的index作参考
                //但是这里是以被移动点进行更新
                arr[j] = tem;
            }

            System.out.println("第"+(++count)+"趟结果：");
            System.out.println(Arrays.toString(arr));
        }

    }

    /**
     * 快速排序--这里的start 和 end 是原来数组中 放入本次快排 的子序列的开始结束下标
     */

    public static void quickSort(int[] arr,int start,int end){
        //arr一直没变 所以无法用arr长度来判断递归结束，只能用长度start<end
//        if (arr.length<2){
//            return;
//        }

        if (start<end){
            int base = arr[start];
            int low = start;
            int high = end;

            while (low < high){
                //1：high所指必须大于base 否则 替换low
                while (low < high && arr[high]>base){
                    high--;
                }

                arr[low] =arr[high];

                //2-替换之后 移动low
                while (low< high && arr[low]<base){
                    low++;
                }
                arr[high] = arr[low];
            }

            //3上面循环直到 low high重叠 将base放入
            arr[low] = base;


            //4递归左边 右边
            quickSort(arr,start,low);
            quickSort(arr,low+1,end);
        }


        //


    }

    /**
     * 归并排序
     * @param arr
     * @param left
     * @param right
     */
    public static void  mergeSort(int[] arr,int left,int right){


        int mid = (left+right)/2;

        //递归分解直到只有一个元素
        if (left<right){
            //System.out.println("left="+left+";mid="+mid);
            //递归分解左边
            mergeSort(arr,left,mid);
            //递归分解右边
            mergeSort(arr,mid+1,right);
            //分完之后开始合
            merge(arr,left,mid,right);

        }


    }
    /**
     *归并排序之核心--合并
     * @param arr 要排序的数组
     * @param left 参与本次归并的左范围
     * @param mid
     * @param right 参与本次归并的右范围

     */
    public static void merge(int[] arr,int left,int mid,int right){

        int[] temp = new int[right-left+1];
        //动态索引
        int i = left;
        int j = mid+1;
        int t = 0;//temp数组中的索引


        //进行循环判断--第一个while中可以取等号
        while (i<=mid && j<=right){

            if (arr[i]<=arr[j]){
                temp[t++] = arr[i];
                i++;
            }else {
                temp[t++] = arr[j];
                j++;
            }
        }
        //把剩余数据加进去

        while (i<=mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j<=right){
            temp[t] = arr[j];
            t++;
            j++;
        }
        //判断完之后将temp覆回arr
        //因为每次参与归并之后temp长度都不一样 所以不能直接赋值
        //只是将传入本次归并的部分进行替换 替换范围就是从 left开始 直到right
        //归并的最后一次才 是0-（n-1）

        for (int k=0;k<temp.length;k++){
            arr[k+left] = temp[k];

        }

    }


    /**
     * 基数排序
     */
    public static void radixSort(int[] arr){
        //定义是个桶 代表0-9 二维数组表示 每一个一位数组表示一个桶 通大小就是数组长度
        int[][] bucket = new int[10][arr.length];

        //另外定一个一维数组 存放每一个桶当前已经存放的数值
        int[] bucketNum = new int[10];

        //最大的数是几位 就要重复几轮，因此需要先得到最大的位数 就是要先找到最大值
        int Max = arr[0];
        for (int num:arr){
            if (num>Max){
                Max = num;
            }
        }
        //计算位数！！！！！牛逼
        int digit =  (Max+"").length();

        //开始循环计算

        for (int round = 0,n = 1;round< digit;round++,n *= 10){

            //开始从个位计算 根据个位将数放在对应桶中
            for (int i=0;i< arr.length;i++){
               // int digitNum = arr[i]/Math.pow(10,i)%10;//可以直接把要除的放在循环for里
                int digitNum = arr[i]/n%10;

                bucket[digitNum][bucketNum[digitNum]] = arr[i];
                bucketNum[digitNum]++;
            }

            //放完之后，从桶中依次取出放回到原来数组
            int count = 0;//存放索引值
            for (int k=0;k<10;k++){

                if (bucketNum[k] == 0){
                    continue;
                }else {
                    for (int l=0;l<bucketNum[k];l++){
                        arr[count++] = bucket[k][l];
                    }
                    //以下写法就出错了
//                for (int num:bucket[k]){
//                }
                }
                //每取完一个桶 当前桶就要清零 否则在下一个位数上就出错了
                bucketNum[k] = 0;
            }

            System.out.println("第"+round+"轮结果"+Arrays.toString(arr));

        }

    }


}
